package MonotonicStack;

import java.util.Stack;

/**
 * @author Lzm
 * @version 1.0
 */
public class largestRectangleArea_ {

  //将heights数组首尾加0, 防止出现不能收获结果的情况
  public int largestRectangleArea(int[] heights) {
    if(heights.length == 1){
      return heights[0];
    }
    int middle = 0;
    int left = 0;
    int right = 0;
    int result = 0;
    int[] newHeights = new int[heights.length + 2];
    Stack<Integer> stack = new Stack<>();
    newHeights[0] = 0;
    newHeights[newHeights.length - 1] = 0;
    for (int i = 0 ; i < heights.length ; i ++){
      newHeights[i + 1] = heights[i];
    }
    stack.push(0);
    for (int i = 0 ; i < newHeights.length; i++){
      if (newHeights[i] >= newHeights[stack.peek()]){
        stack.push(i);
      }
      else{
        while(!stack.isEmpty() && newHeights[i] < newHeights[stack.peek()]){
          middle = stack.pop();
          right = i;
          if (!stack.isEmpty()){
            left = stack.peek();
            result = Math.max(result,newHeights[middle] * (right - left - 1));
          }
        }
        stack.push(i);
      }
    }
    return result;
  }
}
